#include "main.h"

int _buf[1000];

void merge(int* array, int beg1, int len1, int beg2, int len2)
{
	int head1 = beg1;
	int head2 = beg2;
	int headBuf = 0;

	while (head1 < beg1 + len1 && head2 < beg2 + len2)
	{
		if (array[head1] < array[head2])
		{
			_buf[headBuf++] = array[head1++];
		}
		else
		{
			_buf[headBuf++] = array[head2++];
		}
	}
	if (head1 != beg1 + len1)
	{
		while (head1 < beg1 + len1)
		{
			_buf[headBuf++] = array[head1++];
		}
	}
	if (head2 != beg2 + len2)
	{
		while (head2 < beg2 + len2)
		{
			_buf[headBuf++] = array[head2++];
		}
	}

	for (head1 = beg1, headBuf = 0; headBuf < len1 + len2; ++headBuf, ++head1)
	{
		array[head1] = _buf[headBuf];
	}
}

void mergeSort(int* array, int beg, int len)
{
	if (len == 1)
	{
		return;
	}

	int beg1 = beg;
	int len1 = len >> 1;
	int beg2 = beg1 + len1;
	int len2 = len - len1;

	mergeSort(array, beg1, len1);
	mergeSort(array, beg2, len2);

	merge(array, beg1, len1, beg2, len2);
}
